package com.fucius.study.lintcode;

/**
 * 5. 第k大元素
 * 中文English
 * 在数组中找到第 k 大的元素。
 *
 * 样例
 * 样例 1：
 *
 * 输入：
 * n = 1, nums = [1,3,4,2]
 * 输出：
 * 4
 * 样例 2：
 *
 * 输入：
 * n = 3, nums = [9,3,2,4,8]
 * 输出：
 * 4
 * 挑战
 * 要求时间复杂度为O(n)，空间复杂度为O(1)。
 *
 * 注意事项
 * 你可以交换数组中的元素的位置
 */
public class KthLargestElement {
    /**
     * 数组降序 第K大为 nums[k-1]项元素
     *
     * 快速排序：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
     * 通过快速排序的思想
     * 基准点落点坐标为l
     * l=k  return nums[k]
     * l>k  去0,l中找
     * l<k  去l+1,n中找
     *
     * @param n: An integer
     * @param nums: An array
     * @return: the Kth largest element
     */
    public int kthLargestElement(int n, int[] nums) {
        if(n<1||nums==null||n>nums.length){
            return -1;
        }
        int l,len = nums.length;
        int left = 0, right = nums.length-1;
        while(true){
            l = kthLargestElement(left,right,nums);
            if(l+1==n){
                return nums[l];
            }
            if(l+1<n){
                left = l + 1;
            }
            if(l+1>n){
                right = l - 1;
            }
        }
    }

    /**
     * 返回nums[left]在nums中的有序位置
     * @param left
     * @param right
     * @param nums
     * @return
     */
    public int kthLargestElement(int left,int right, int[] nums) {
        //基准点
        int l = left;
        int mark = nums[l];
        boolean flag = true;
        while(left<right){
            /*
                比基准点大的放左边
                比基准点小的放右边
             */
            if (flag) {
                if (nums[right]<=mark) {
                    right--;
                }else{
                    nums[l] = nums[right];
                    nums[right] = mark;
                    l = right;
                    flag=false;
                }
            }else{
                if (nums[left]>=mark) {
                    left++;
                }else{
                    nums[l] = nums[left];
                    nums[left] = mark;
                    l = left;
                    flag = true;
                }
            }
        }
        return l;
    }

    public static void main(String[] args) {
        int n = 1;
        int[] nums = {1,3,4,2};
        System.out.println(new KthLargestElement().kthLargestElement(n,nums));
    }
}
